/**
 * @author LKQ
 * @date 2022/1/2 10:07
 * @description
 */
public class FormalSolution {
    public static void main(String[] args) {
        FormalSolution solution = new FormalSolution();
        System.out.println(solution.lastRemaining(1000));
    }
    public int lastRemaining(int n) {
        // 利用等差数列的特性，每次间隔删除后公差越来越大。
        int a1 = 1, an = n;
        // cnt为元素数目，step为公差，k判断为正向删除还反向
        int k = 0, cnt = n, step = 1;
        while (cnt > 1) {
            if (k % 2 == 0) {
                // 正向删除，队首元素变成下一个，an根据元素个数，若奇数个，则为倒数第二个，偶数个则不变
                a1 = a1 + step;
                an = (cnt % 2 == 0) ? an : an - step;
            } else {
                // 反向删除，a1根据元素个数，若偶数个，则不变，否则a1变成下一个；an肯定要删除
                a1 = (cnt % 2 == 0) ? a1 : a1 + step;
                an = an - step;
            }
            k++;
            // 右移除以2，每次删除后元素个数减半，若cnt = 31, 则变换后为15个
            cnt = cnt >> 1;
            // 左移乘以2，公差每次变大一倍。
            step = step << 1;
        }
        return a1;
    }
}
